const nodeType = {
    operator: 0,//操作符
    operand: 1//操作数
}
function BTNode(value, type, left = null, right = null) {
    this.value = value; // 节点的值，例如对于操作符节点，可能的取值为： + 、-、*、/
    this.type = type; // 节点类型，取值为 nodeType.operator or nodeType.operand
    this.left = left; // 左子节点
    this.right = right; // 右子节点
}
const operReg = /[\+\*\/\(\)]/;
const isOper = t => operReg.test(t);//判断是不是操作符

// 将字符串表达式转换成二叉树
const shouldMerge = node => node &&
    node.type === nodeType.operator &&
    (node.value === '*' || node.value === '/');

function toBT(expr) {
    const tokens = expr.replace(/\-/g,'+-') //将减号替换为加减号组合
        .replace(/\*\+/g,'*').replace(/\/\+/g,'/')
        .replace(/^\+/,'') //去除首个加号，如果有的话
        .replace(/[\+\*\/\(\)]/g, _ => ` ${_} `) //运算符两边加空格
        .trim()  // 去除首尾空格
        .split(/ +/) // 以空格进行切割
        .map(t => t.trim()); // 切割后去除空格
    console.log(tokens);
    const nodes = [];
    for (let token of tokens) {
        if (isOper(token)) {
            const node = new BTNode(token, nodeType.operator, nodes.pop());
            nodes.push(node);
        } else if (token === '(') {
            nodes.push('(');
        } else if (token === ')') {
            let node = nodes.pop();
            let preNode;
            try {
                while ((preNode = nodes.pop()) !== '(') {
                    preNode.right = node;
                    node = preNode;
                }
            } catch (err) {
                throw 'bracket count not match';
            }
            const top = nodes[nodes.length - 1];
            if (shouldMerge(top)) {
                top.right = node;
            } else {
                nodes.push(node);
            }
        } else {
            const value = parseFloat(token);
            if (Number.isNaN(value)) {
                throw `Invalid express for '${token}'`;
            }
            const node = new BTNode(value, nodeType.operand);
            const top = nodes[nodes.length - 1];
            if (shouldMerge(top)) {
                top.right = node;
            } else {
                nodes.push(node);
            }
        }
    }
    for (let i = 0; i < nodes.length - 1; i++) {
        const node = nodes[i];
        node.right = nodes[i + 1];
    }
    return nodes[0];
}

const proto = BTNode.prototype;
proto.nodeType = nodeType;
// 中序遍历
proto.middleTraverse = function () {
    return traverse(this, 'middle');
}
// 前序遍历
proto.forwardTraverse = function () {
    return traverse(this, 'forward');
}
// 后序遍历
proto.backwardTraverse = function () {
    return traverse(this, 'backward');
}
function traverse(node, type = 'mid') {
    if (!node instanceof BTNode) {
        throw `The param 'node' must be type of BTNode`;
    }
    if (node.type === nodeType.operand) {
        return [node.value];
    }
    switch (type) {
        case 'forward':
            return [node.value, ...traverse(node.left, type), ...traverse(node.right, type)];
        case 'middle':
            return [...traverse(node.left, type), node.value, ...traverse(node.right, type)];
        case 'backward':
            return [...traverse(node.left, type), ...traverse(node.right, type), node.value];
    }
}
//后序表达式的求值
// 遍历后序表达式中的每一个元素：
// （1）如果是操作数则直接压入栈中，
// （2）如果时操作符，从栈顶中取出两个元素，并进行操作符对应的运算，并将运算结果重新压入栈中；
function evalBackwardExpression(exprs) {
    const exprsStack = [];
    for (let token of exprs) {
        if (isOper(token)) {
            const rNum = exprsStack.pop();
            const lNum = exprsStack.pop();
            let result;
            switch (token) {
                case '+':
                    result = lNum + rNum;
                    break;
                case '-':
                    result = lNum - rNum;
                    break;
                case '*':
                    result = lNum * rNum;
                    break;
                case '/':
                    result = lNum / rNum;
                    break;
            }
            exprsStack.push(result);
        } else {
            exprsStack.push(token);
        }
    }
    return exprsStack[0];
}
function computeStr(str){
    // console.log(str);
    return evalBackwardExpression(toBT(str).backwardTraverse())
}